/******************************************************************************************************
*******************************************************************************************************
**************************************                        *****************************************
**************************************     DECOMPRESSING      *****************************************
**************************************                        *****************************************
*******************************************************************************************************
******************************************************************************************************/
#include <stdio.h>
#include <iostream.h>
#include <process.h>
#include <stdlib.h>
#include <string.h>
#include <alloc.h>
#define BITS 12                   
#define HASHING_SHIFT BITS-8      
#define MAX_VALUE (1 << BITS) - 1 
#define MAX_CODE MAX_VALUE - 1    
				  
#if BITS == 14
  #define TABLE_SIZE 18041        /* Setting the number of bits to 12, 13 or 14 */
#endif                            
#if BITS == 13                    
  #define TABLE_SIZE 9029
#endif
#if BITS <= 12
  #define TABLE_SIZE 5021
#endif

void *malloc();

int *code_value;                  /* This is the code value array        */
unsigned int *prefix_code;        /* This array holds the prefix codes   */
unsigned char *append_character;  /* This array holds the appended chars */
unsigned char decode_stack[4000]; /* This array holds the decoded string */


class Decompression
{
	public :


/************************************************************************************
      This routine simply decodes a string from the string table, storingit in a buffer.
        The buffer can then be output in reverse order by the expansion program.             
         ******************************************************************************/

	char *decode_string(unsigned char *buffer,unsigned int code)
	{
		int i;

		i=0;
		while (code > 255)
		{
			*buffer++ = append_character[code];
			code=prefix_code[code];
			if (i++>=4094)
			{
				cout <<"Fatal error during code expansion.\n";
				exit(1);
			}
		}
		*buffer=code;
		return(buffer);
	}
  /************************************************************************
   **
   ** 
   **                     This is the expansion routine.   
   **   
   **      It takes an LZW format file, and expandsit to an output file.
   **
   *************************************************************************/

	expand(FILE *input,FILE *output)
	{
		unsigned int next_code;
		unsigned int new_code;
		unsigned int old_code;
		int character;
		int counter;
		unsigned char *string;
 //		char *decode_string(unsigned char *buffer,unsigned int code);

		next_code=256;           /* This is the next available code to define */
		counter=0;               /* Counter is used as a pacifier.            */
		cout <<"Expanding...\n";

		old_code=input_code(input);  /* Read in the first code, initialize the */
		character=old_code;          /* character variable, and send the first */
		putc(old_code,output);       /* code to the output file                */

         /************************************************************************************
              This is the main expansion loop.  It reads in characters from the LZW file
             until it sees the special code used to inidicate the end of the data.                         
         ******************************************************************************/
		while ((new_code=input_code(input)) != (MAX_VALUE))
		{
			if (++counter==1000)   /* This section of code prints out     */
			{                      /* an asterisk every 1000 characters   */
				counter=0;           /* It is just a pacifier.              */
				cout <<"*";
			}
/************************************************************************************
              This code checks for the special STRING+CHARACTER+STRING+CHARACTER+STRING
                  case which generates an undefined code.  It handles it by decoding
              the last code, and adding a single character to the end of the decode string.    
         ******************************************************************************/
			if (new_code>=next_code)
			{
				*decode_stack=character;
				string=decode_string(decode_stack+1,old_code);
			}
/************************************************************************************
                     Otherwise we do a straight decode of the new code.                         
         ******************************************************************************/
			
                        else
				string=decode_string(decode_stack,new_code);

/************************************************************************************
                    Now we output the decoded string in reverse order.                     
         ******************************************************************************/

			character=*string;
			while (string >= decode_stack)
				putc(*string--,output);

/************************************************************************************
                   Finally, if possible, add a new code to the string table.                  
         ******************************************************************************/

			if (next_code <= MAX_CODE)
			{
				prefix_code[next_code]=old_code;
				append_character[next_code]=character;
				next_code++;
			}
			old_code=new_code;
		}
		cout <<"\n";
	}


/************************************************************************************
                The following routine is used to output variable length codes.   
       ******************************************************************************/

	input_code(FILE *input)
	{
		unsigned int return_value;
		static int input_bit_count=0;
		static unsigned long input_bit_buffer=0L;

		while (input_bit_count <= 24)
		{
			input_bit_buffer |=
			(unsigned long) getc(input) << (24-input_bit_count);
			input_bit_count += 8;
		}
		return_value=input_bit_buffer >> (32-BITS);
		input_bit_buffer <<= BITS;
		input_bit_count -= BITS;
		return(return_value);
	}

	output_code(FILE *output,unsigned int code)
	{
		static int output_bit_count=0;
		static unsigned long output_bit_buffer=0L;

		output_bit_buffer |= (unsigned long) code << (32-BITS-output_bit_count);
		output_bit_count += BITS;
		while (output_bit_count >= 8)
		{
			putc(output_bit_buffer >> 24,output);
			output_bit_buffer <<= 8;
			output_bit_count -= 8;
		}
	}
}
//////////////////////////////////////////////
main(int argc, char *argv[])
{
	Decompression Dcom;
	FILE *input_file;
	FILE *output_file;
	FILE *lzw_file;
	char input_file_name[81];

/****************************************************************************
                          The three buffers are needed for the compression phase.
         ******************************************************************************/

	code_value=(int*)malloc(TABLE_SIZE*sizeof(unsigned int));
	prefix_code=(unsigned int*)malloc(TABLE_SIZE*sizeof(unsigned int));
	append_character=(char *)malloc(TABLE_SIZE*sizeof(unsigned char));
	if (code_value==NULL || prefix_code==NULL || append_character==NULL)
	{
		cout <<"Fatal error allocating table space!\n";
		exit(1);
	}



         /****************************************************************************
                           Now open the files for the expansion.
         ******************************************************************************/

	lzw_file=fopen("test.lzw","rb");
	output_file=fopen("test.out","wb");
	if (lzw_file==NULL || output_file==NULL)
	{
		cout <<"Fatal error opening files.\n";
		exit(1);
	}

         /****************************************************************************
                                          Expand the file.
         ******************************************************************************/

	Dcom.expand(lzw_file,output_file);
	fclose(lzw_file);
	fclose(output_file);

	free(prefix_code);
	free(append_character);
}
